#include <vector>
#include <algorithm>

using namespace std;

/* 基数排序 */
void radixSort(vector<int>& nums) {
    int m = *max_element(nums.begin(), nums.end());
    for (int exp = 1; exp <= m; exp *= 10)
        countingSortDigit(nums, exp);
}

/* 计数排序（根据 nums 第 k 位排序） */
void countingSortDigit(vector<int>& nums, int exp) {
    vector<int> counter(10, 0);
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        int d = digit(nums[i], exp);
        counter[d]++;
    }
    for (int i = 1; i < 10; i++) {
        counter[i] += counter[i - 1];
    }
    vector<int> res(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        int d = digit(nums[i], exp);
        int j = counter[d] - 1;
        res[j] = nums[i];
        counter[d]--;
    }
    for (int i = 0; i < n; i++)
        nums[i] = res[i];
}

/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
int digit(int num, int exp) {
    return (num / exp) % 10;
}
